// ？
#include <bits/stdc++.h>
using namespace std;
int dp[1005];
string s;
int t;
// 判断s字符串从l到r是否是回文串
bool f(int l, int r) {
  while (l < r) {
    if (s[l] != s[r]) {
      return false;
    }
    l++;
    r--;
  }
  return true;
}
int main() {
  cin >> t;
  while (t--) {
    cin >> s;
    int len = s.length();
    s = ' ' + s; // 下标改成从1开始
    for (int i = 1; i <= len; i++) {
      // 长度为i的字符串，最多用i-1次分割为回文串（分成单个字符）
      dp[i] = i - 1;
    }
    dp[0] = 0;
    for (int i = 1; i <= len; i++) {
      for (int j = i - 1; j >= 1; j--) {
        if (f(j, i)) {  // 如果s字串从j到i是回文串
          if (j == 1) { // 到头全是回文
            dp[i] = 0;  // 0次
          } else {      // 否则，取以j为分割点的最小值
            dp[i] = min(dp[i], dp[j - 1] + 1);
          }
        }
      }
    }
    cout << dp[len] << endl;
  }
  return 0;
}